{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #与非的谜题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getNandResult"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #与非的谜题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在永恒之森中，封存着有关万灵之树线索的卷轴，只要探险队通过最后的考验，便可以获取前往万灵之树的线索。\n",
    "\n",
    "探险队需要从一段不断变化的谜题数组中找到最终的密码，初始的谜题为长度为 `n` 的数组 `arr`（下标从 0 开始），数组中的数字代表了 `k` 位二进制数。\n",
    "破解谜题的过程中，需要使用 `与非（NAND）` 运算方式，`operations[i] = [type,x,y]` 表示第 `i` 次进行的谜题操作信息：\n",
    "- 若 `type = 0`，表示修改操作，将谜题数组中下标 `x` 的数字变化为 `y`；\n",
    "- 若 `type = 1`，表示运算操作，将数字 `y` 进行 `x*n` 次「与非」操作，第 `i` 次与非操作为 `y = y NAND arr[i%n]`；\n",
    "    > 运算操作结果即：`y NAND arr[0%n] NAND arr[1%n] NAND arr[2%n] ... NAND arr[(x*n-1)%n]`\n",
    "\n",
    "最后，将所有运算操作的结果按顺序逐一进行 `异或（XOR）`运算，从而得到最终解开封印的密码。请返回最终解开封印的密码。\n",
    "\n",
    "**注意:**\n",
    "- 「与非」（NAND）的操作为：先进行 `与` 操作，后进行 `非` 操作。\n",
    "    > 例如：两个三位二进制数`2`和`3`，其与非结果为 `NOT ((010) AND (011)) = (101) = 5`\n",
    "\n",
    "**示例 1：**\n",
    "> 输入: \n",
    "> `k = 3`\n",
    "> `arr = [1,2]`\n",
    "> `operations = [[1,2,3],[0,0,3],[1,2,2]]`\n",
    ">\n",
    "> 输出: `2`\n",
    ">\n",
    "> 解释：\n",
    "> 初始的谜题数组为 [1,2]，二进制位数为 3，\n",
    "> 第 0 次进行运算操作，将数字 3(011) 进行 2\\*2 次「与非」运算，\n",
    "> 运算操作结果为 `3 NAND 1 NAND 2 NAND 1 NAND 2 = 5`\n",
    "> 第 1 次进行修改操作，谜题数组的第 `0` 个数字变化为 `3`，谜题变成 `[3,2]`\n",
    "> 第 2 次进行运算操作，将数字 2(010) 进行 2\\*2 次「与非」运算，\n",
    "> 运算操作结果为 `2 NAND 3 NAND 2 NAND 3 NAND 2 = 7`\n",
    "> 所有运算操作结果进行「异或」运算为 `5 XOR 7 = 2`\n",
    "> 因此得到的最终密码为 `2`。\n",
    "\n",
    "**示例 2：**\n",
    "> 输入:\n",
    "> `k = 4`\n",
    "> `arr = [4,6,4,7,10,9,11]`\n",
    "> `operations = [[1,5,7],[1,7,14],[0,6,7],[1,6,5]]`\n",
    "> 输出: `9`\n",
    "> 解释: \n",
    "> 初始的谜题数组为 [4,6,4,7,10,9,11],\n",
    "> 第 0 次进行运算操作，运算操作结果为 5；\n",
    "> 第 1 次进行运算操作，运算操作结果为 5；\n",
    "> 第 2 次进行修改操作，修改后谜题数组为 [4, 6, 4, 7, 10, 9, 7]；\n",
    "> 第 3 次进行运算操作，运算操作结果为 9；\n",
    "> 所有运算操作结果进行「异或」运算为 `5 XOR 5 XOR 9 = 9`；\n",
    "> 因此得到的最终密码为 `9`。\n",
    "\n",
    "**提示:**\n",
    "- `1 <= arr.length, operations.length <= 10^4`\n",
    "- `1 <= k <= 30`\n",
    "- `0 <= arr[i] < 2^k`\n",
    "- 若 `type = 0`，`0 <= x < arr.length` 且 `0 <= y < 2^k`\n",
    "- 若 `type = 1`，`1 <= x < 10^9` 且 `0 <= y < 2^k`\n",
    "- 保证存在 `type = 1` 的操作\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ryfUiz](https://leetcode.cn/problems/ryfUiz/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ryfUiz](https://leetcode.cn/problems/ryfUiz/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[1,2]\\n[[1,2,3],[0,0,3],[1,2,2]]', '4\\n[4,6,4,7,10,9,11]\\n[[1,5,7],[1,7,14],[0,6,7],[1,6,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:\n",
    "\n",
    "        n, m = len(arr), (1 << k) - 1\n",
    "        a, b = 0, m\n",
    "        prefix1, prefix2 = [0], [m]\n",
    "\n",
    "        def nand(x, y):\n",
    "            return ~(x & y) & m\n",
    "\n",
    "        for i in range(n):\n",
    "            a = nand(a, arr[i])\n",
    "            b = nand(b, arr[i])\n",
    "            prefix1.append(a)\n",
    "            prefix2.append(b)\n",
    "        suf = [prefix1[-1], prefix2[-1]]\n",
    "\n",
    "        ans = 0\n",
    "        for type, x, y in operations:\n",
    "            if type == 0:\n",
    "                arr[x] = y\n",
    "                a, b = prefix1[x], prefix2[x]\n",
    "                for j in range(x, n):\n",
    "                    a = nand(a, arr[j])\n",
    "                    b = nand(b, arr[j])\n",
    "                    if prefix1[j + 1] == a and prefix2[j + 1] == b:\n",
    "                        break\n",
    "                    prefix1[j + 1] = a\n",
    "                    prefix2[j + 1] = b\n",
    "                suf = [prefix1[-1], prefix2[-1]]\n",
    "            else:\n",
    "                c = 0\n",
    "                if x & 1:\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                else:\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                    y = c\n",
    "                    c = 0\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                ans ^= c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:\n",
    "        n, m = len(arr), (1 << k) - 1\n",
    "        a, b = 0, m\n",
    "        prefix1, prefix2 = [0], [m]\n",
    "\n",
    "        def nand(x, y):\n",
    "            return ~(x & y) & m\n",
    "\n",
    "        for i in range(n):\n",
    "            a = nand(a, arr[i])\n",
    "            b = nand(b, arr[i])\n",
    "            prefix1.append(a)\n",
    "            prefix2.append(b)\n",
    "        suf = [prefix1[-1], prefix2[-1]]\n",
    "\n",
    "        ans = 0\n",
    "        for type, x, y in operations:\n",
    "            if type == 0:\n",
    "                arr[x] = y\n",
    "                a, b = prefix1[x], prefix2[x]\n",
    "                for j in range(x, n):\n",
    "                    a = nand(a, arr[j])\n",
    "                    b = nand(b, arr[j])\n",
    "                    # 不加这一句会超时~\n",
    "                    if prefix1[j + 1] == a and prefix2[j + 1] == b:\n",
    "                        break\n",
    "                    prefix1[j + 1] = a\n",
    "                    prefix2[j + 1] = b\n",
    "                suf = [prefix1[-1], prefix2[-1]]\n",
    "            else:\n",
    "                c = 0\n",
    "                if x & 1:\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                else:\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                    y = c\n",
    "                    c = 0\n",
    "                    for i in range(k):\n",
    "                        c |= (suf[y >> i & 1] >> i & 1) << i\n",
    "                # print(c, end=',')\n",
    "                ans ^= c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:\n",
    "        N = len(arr)\n",
    "\n",
    "        # 二进制分解\n",
    "        def fj2(n):\n",
    "            ret = [0] * k\n",
    "            i = 0\n",
    "\n",
    "            while n:\n",
    "                n, m = divmod(n, 2)\n",
    "                ret[i] = m\n",
    "                i += 1\n",
    "\n",
    "            return ret\n",
    "\n",
    "        # 分解arr\n",
    "        l_fj = [fj2(n) for n in arr]\n",
    "\n",
    "        # 一系列数的NAND结果如下：\n",
    "        # 1. 若最后一个为0，则肯定为1\n",
    "        # 2. 若最后一个为1，则向前查找连续的1，若后面还有2个或者以上数，偶数个数再加1\n",
    "        #    偶数个1为0，奇数个1位1\n",
    "\n",
    "        # 记录连续的1区间\n",
    "        class QJ:\n",
    "            def __init__(self):\n",
    "                # 偶数下标为开始，奇数下标为结束，闭区间\n",
    "                self.l = []\n",
    "\n",
    "            def add(self, i):\n",
    "                if self.l and self.l[-1] == i - 1:\n",
    "                    self.l[-1] = i\n",
    "                else:\n",
    "                    self.l += [i, i]\n",
    "\n",
    "            # 修改为0，保证原来为1\n",
    "            def set_0(self, i):\n",
    "                p = bisect.bisect_left(self.l, i)\n",
    "\n",
    "                if self.l[p] == i:\n",
    "                    if p % 2:\n",
    "                        # 最后一个，并且开始和结束不相等\n",
    "                        self.l[p] = i - 1\n",
    "                    elif self.l[p + 1] == i:\n",
    "                        # 开始和结束相等\n",
    "                        del self.l[p:p + 2]\n",
    "                    else:\n",
    "                        # 第一个，并且开始和结束不相等\n",
    "                        self.l[p] = i + 1\n",
    "                else:\n",
    "                    self.l.insert(p, i + 1)\n",
    "                    self.l.insert(p, i - 1)\n",
    "\n",
    "            # 修改为1，保证原来为0\n",
    "            def set_1(self, i):\n",
    "                p = bisect.bisect_left(self.l, i)\n",
    "\n",
    "                if p == 0:\n",
    "                    if self.l and self.l[0] == i + 1:\n",
    "                        # 和第一和重合\n",
    "                        self.l[0] = i\n",
    "                    else:\n",
    "                        self.l.insert(0, i)\n",
    "                        self.l.insert(0, i)\n",
    "\n",
    "                    return\n",
    "\n",
    "                if p == len(self.l):\n",
    "                    if self.l[p - 1] == i - 1:\n",
    "                        # 和前一个重合\n",
    "                        self.l[p - 1] = i\n",
    "                    else:\n",
    "                        self.l.insert(p, i)\n",
    "                        self.l.insert(p, i)\n",
    "\n",
    "                    return\n",
    "\n",
    "                if self.l[p - 1] == i - 1:\n",
    "                    # 和结束差1\n",
    "                    if self.l[p] == i + 1:\n",
    "                        # 修改后和下一个重合\n",
    "                        del self.l[p - 1:p + 1]\n",
    "                    else:\n",
    "                        self.l[p - 1] = i\n",
    "                elif self.l[p] == i + 1:\n",
    "                    # 修改后和下一个重合:\n",
    "                    self.l[p] = i\n",
    "                else:\n",
    "                    self.l.insert(p, i)\n",
    "                    self.l.insert(p, i)\n",
    "\n",
    "        l_qj = [QJ() for _ in range(k)]\n",
    "\n",
    "        # 0 ~ N - 1\n",
    "        for i, fj in enumerate(l_fj):\n",
    "            for j, v in enumerate(fj):\n",
    "                if v:\n",
    "                    l_qj[j].add(i)\n",
    "\n",
    "        # 返回值\n",
    "        ret = [0] * k\n",
    "\n",
    "        for t, x, y in operations:\n",
    "            fjy = fj2(y)\n",
    "\n",
    "            if t == 0:\n",
    "                for i, (vx, vy) in enumerate(zip(l_fj[x], fjy)):\n",
    "                    if vx != vy:\n",
    "                        if vx == 0:\n",
    "                            l_qj[i].set_1(x)\n",
    "                        else:\n",
    "                            l_qj[i].set_0(x)\n",
    "\n",
    "                l_fj[x] = fjy\n",
    "\n",
    "            else:\n",
    "                for i, v in enumerate(l_fj[-1]):\n",
    "                    if v == 0:\n",
    "                        fjy[i] = 1\n",
    "                    else:\n",
    "                        num = N - l_qj[i].l[-2]\n",
    "                        if num == N:\n",
    "                            # arr中该bit全为1\n",
    "                            num = x * N + fjy[i]\n",
    "                        else:\n",
    "                            num += 1\n",
    "\n",
    "                        fjy[i] = num % 2\n",
    "\n",
    "                # 异或\n",
    "                # print(fjy)\n",
    "                for i, v in enumerate(fjy):\n",
    "                    ret[i] ^= v\n",
    "\n",
    "        # 计算返回值\n",
    "        ans = 0\n",
    "        n = 1\n",
    "\n",
    "        for v in ret:\n",
    "            ans += n * v\n",
    "            n *= 2\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/home/guoyf/anaconda3/bin/python3\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:\n",
    "        def setBit(interval:SortedList, idx:int):\n",
    "            i = interval.bisect_left([idx, 0]) - 1\n",
    "            if interval[i][-1] >= idx:\n",
    "                return\n",
    "            if interval[i][-1] == idx - 1:\n",
    "                if i < len(interval) - 1 and interval[i + 1][0] == idx + 1:\n",
    "                    interval[i][-1] = interval[i + 1][1]\n",
    "                    interval.pop(i + 1)\n",
    "                    return\n",
    "                interval[i][-1] = idx\n",
    "                return\n",
    "            if i < len(interval) - 1 and interval[i + 1][0] <= idx + 1:\n",
    "                interval[i + 1][0] = idx\n",
    "            else:\n",
    "                interval.add([idx, idx])\n",
    "\n",
    "        def resetBit(interval:SortedList, idx:int):\n",
    "            i = interval.bisect_left([idx, 0]) - 1\n",
    "            if i < len(interval) - 1 and interval[i + 1][0] == idx:\n",
    "                if interval[i + 1][1] == idx:\n",
    "                    interval.pop(i + 1)\n",
    "                    return\n",
    "                interval[i + 1][0] = idx + 1\n",
    "                return\n",
    "            if interval[i][-1] >= idx:\n",
    "                a = interval[i][0]\n",
    "                b = idx - 1\n",
    "                c = idx + 1\n",
    "                d = interval[i][1]\n",
    "                interval.pop(i)\n",
    "                if b >= a:\n",
    "                    interval.add([a, b])\n",
    "                if d >= c:\n",
    "                    interval.add([c, d])\n",
    "\n",
    "        inters = [SortedList() for _ in range(k)]\n",
    "        for j in range(k):\n",
    "            inters[j].add([-3, -3])\n",
    "        N = len(arr)\n",
    "        for i, num in enumerate(arr):\n",
    "            mask = 1\n",
    "            for j in range(k):\n",
    "                if mask & num > 0:\n",
    "                    if inters[j][-1][-1] == i - 1:\n",
    "                        inters[j][-1][-1] = i\n",
    "                    else:\n",
    "                        inters[j].add([i, i])\n",
    "                mask += mask\n",
    "        \n",
    "        # print('--')\n",
    "        # for l in inters:\n",
    "        #     print(*list(l))\n",
    "        # print('--')\n",
    "        result = 0\n",
    "        for cmd, x, y in operations:\n",
    "            # print(f'cmd = {cmd}, x = {x}, y = {y}')\n",
    "            if cmd == 1:\n",
    "                num = 2 ** k - 1\n",
    "                mask = 1\n",
    "                for j in range(k):\n",
    "                    if inters[j][-1][-1] == N - 1:\n",
    "                        l = inters[j][-1][-1] - inters[j][-1][0] + 1\n",
    "                        if l < N and l % 2 == 1:\n",
    "                            num ^= mask\n",
    "                        if l == N and (x * l + int(mask & y > 0)) % 2 == 0:\n",
    "                            num ^= mask\n",
    "                        # if (inters[j][-1][-1] - inters[j][-1][0]) % 2 == 0:\n",
    "                        #     num ^= mask\n",
    "                    mask += mask\n",
    "                result ^= num\n",
    "                # print(f'num = {num}:{bin(num)}, result = {result}')\n",
    "            else:\n",
    "                mask = 1\n",
    "                for j in range(k):\n",
    "                    if y & mask > 0:\n",
    "                        setBit(inters[j], x)\n",
    "                    else:\n",
    "                        resetBit(inters[j], x)\n",
    "                        # pass\n",
    "                    mask += mask\n",
    "            # print(inters)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "# from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:\n",
    "        def setBit(interval:SortedList, idx:int):\n",
    "            i = interval.bisect_left([idx, 0]) - 1\n",
    "            if interval[i][-1] >= idx:\n",
    "                return\n",
    "            if interval[i][-1] == idx - 1:\n",
    "                if i < len(interval) - 1 and interval[i + 1][0] == idx + 1:\n",
    "                    interval[i][-1] = interval[i + 1][1]\n",
    "                    interval.pop(i + 1)\n",
    "                    return\n",
    "                interval[i][-1] = idx\n",
    "                return\n",
    "            if i < len(interval) - 1 and interval[i + 1][0] <= idx + 1:\n",
    "                interval[i + 1][0] = idx\n",
    "            else:\n",
    "                interval.add([idx, idx])\n",
    "\n",
    "        def resetBit(interval:SortedList, idx:int):\n",
    "            i = interval.bisect_left([idx, 0]) - 1\n",
    "            if i < len(interval) - 1 and interval[i + 1][0] == idx:\n",
    "                if interval[i + 1][1] == idx:\n",
    "                    interval.pop(i + 1)\n",
    "                    return\n",
    "                interval[i + 1][0] = idx + 1\n",
    "                return\n",
    "            if interval[i][-1] >= idx:\n",
    "                a = interval[i][0]\n",
    "                b = idx - 1\n",
    "                c = idx + 1\n",
    "                d = interval[i][1]\n",
    "                interval.pop(i)\n",
    "                if b >= a:\n",
    "                    interval.add([a, b])\n",
    "                if d >= c:\n",
    "                    interval.add([c, d])\n",
    "\n",
    "        inters = [SortedList() for _ in range(k)]\n",
    "        for j in range(k):\n",
    "            inters[j].add([-3, -3])\n",
    "        N = len(arr)\n",
    "        for i, num in enumerate(arr):\n",
    "            mask = 1\n",
    "            for j in range(k):\n",
    "                if mask & num > 0:\n",
    "                    if inters[j][-1][-1] == i - 1:\n",
    "                        inters[j][-1][-1] = i\n",
    "                    else:\n",
    "                        inters[j].add([i, i])\n",
    "                mask += mask\n",
    "        \n",
    "        result = 0\n",
    "        for cmd, x, y in operations:\n",
    "            if cmd == 1:\n",
    "                num = 2 ** k - 1\n",
    "                mask = 1\n",
    "                for j in range(k):\n",
    "                    if inters[j][-1][-1] == N - 1:\n",
    "                        l = inters[j][-1][-1] - inters[j][-1][0] + 1\n",
    "                        if l < N and l % 2 == 1:\n",
    "                            num ^= mask\n",
    "                        if l == N and (x * l + int(mask & y > 0)) % 2 == 0:\n",
    "                            num ^= mask\n",
    "                    mask += mask\n",
    "                result ^= num\n",
    "            else:\n",
    "                mask = 1\n",
    "                for j in range(k):\n",
    "                    if y & mask > 0:\n",
    "                        setBit(inters[j], x)\n",
    "                    else:\n",
    "                        resetBit(inters[j], x)\n",
    "                    mask += mask\n",
    "        return result\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
